// 四大遍历：1.前序遍历；2.中序遍历；3.后序遍历；4.层序遍历 5.对称遍历；
// 递归版本与非递归版本实现；


#include <iostream>
#include <math.h>
#include <array>
#include <set>
#include <queue>
#include <stack>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};

void preOrderUnRecur(TreeNode* head) {
    if (head == nullptr) {
        return;
    }
    std::cout << head->val << " " << std::endl;
    preOrderUnRecur(head->left);
    preOrderUnRecur(head->right);
}

void preOrderUnRecur(TreeNode* head) {
    std::cout << "pre-order:"<< std::endl;
    if (head == nullptr) return;
    stack<TreeNode*> node_stack;
    node_stack.push(head);
    TreeNode* cur = head;
    while(!node_stack.empty()) {
        cur = node_stack.top();
        node_stack.pop();
        std::cout << cur->val << " " ;
        if(cur->right) {
            node_stack.push(cur->right);
        }
        if(cur->left) {
            node_stack.push(cur->left);
        }  
    }
    std::cout << std::endl;
}

void inOrderUnRecur(TreeNode* head) {
    if (head == nullptr) {
        return;
    }
    inOrderUnRecur(head->left);
    std::cout << head->val << " " << std::endl;
    inOrderUnRecur(head->right);
}

void inOrderUnRecur(TreeNode* head) {
    std::cout << "in-order:"<< std::endl;
    if (head == nullptr) return;
    stack<TreeNode*> node_stack;
    TreeNode* cur = head;
    while(!node_stack.empty() || cur != nullptr) {
       if(cur != nullptr) {
            node_stack.push(cur);
            cur=cur->left;
       }else{
         cur = node_stack.top();
         node_stack.pop();
         std::cout << cur->val + " ";
         cur = cur->right;
       }
    }
    std::cout << std::endl;
}

void posOrderUnRecur(TreeNode* head) {
    if (head == nullptr) {
        return;
    }
    posOrderUnRecur(head->left);
    posOrderUnRecur(head->right);
    std::cout << head->val << " " << std::endl;
}

void posOrderUnRecur(TreeNode* head) {
    std::cout << "pos-order:"<< std::endl;
    if (head == nullptr) return;
    stack<TreeNode*> node_stack;
    stack<TreeNode*> help_stack;
    TreeNode* cur = head;
    node_stack.push(cur);

    while(!node_stack.empty()) {
        cur = node_stack.top();
        node_stack.pop();
        help_stack.push(cur);
        if (cur->left) {
            node_stack.push(cur->left);
        }
        if (cur->right) {
            node_stack.push(cur->right);
        }
    }
    while(!help_stack.empty()) {
        cur = help_stack.top();
        help_stack.pop();
        std::cout << cur->val << " " << std::endl;
    }
}
// 层序遍历
#include <queue>
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
		std::vector<int> res_vec;
		if (root == nullptr) return res_vec;
		std::queue<TreeNode*> t_queue;
		t_queue.push(root);
		while(!t_queue.empty()) {
			auto cur_node = t_queue.front();
			res_vec.push_back(cur_node->val);
			t_queue.pop();
			if (cur_node->left) {
				t_queue.push(cur_node->left);
			}
			if (cur_node->right) {
				t_queue.push(cur_node->right);
			}
		}
		return res_vec;
    }
};

// 对称遍历
void preOrderUnRecur(TreeNode* head) {
    if (head == nullptr) {
        return;
    }
    std::cout << head->val << " " << std::endl;
    preOrderUnRecur(head->right);
    preOrderUnRecur(head->left);
}